package tu.shortestPath;

// import linjiebiao.biao.ALGraph;

public class ShortestPath_Dij {
    public final static int INFINITY = Integer.MAX_VALUE;
    public int[] Dijkstra(int[][] jz_time, int start, Object[] temp, int arr, boolean least) throws Exception {
        if(start < 0 || arr <0 ) {
            throw new Exception("请输入正确的起始/终点站");
        }
        if(start == arr){
            throw new Exception("请输入正确的路径");
        }
        int n = jz_time.length;         //顶点个数
        int[] shortPath = new int[n];   //存放最短路径
        String[] path = new String[n];  //存放最短路径的字符串提示
        // String start1;
        for(int i = 0; i < n; i++)      
            path[i] = new String(temp[start]+"--->" + temp[i]);
        int[] visited = new int[n];         //标记当前顶点

        //初始化
        shortPath[start] = 0;
        visited[start] = 1;

        for (int count = 1; count <= n - 1; count++){   //加入n-1个顶点
            int k = -1;         //选出距离初始顶点start的最近的未标记顶点
            int dmin = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if(visited[i] == 0 && jz_time[start][i] < dmin){
                    dmin = jz_time[start][i];
                    k = i;
                }
            }
            // System.out.println("k=" + k);
            //将选出的顶点标记为以求出的最短路径，最短路径为start到dmin
            shortPath[k] = dmin;
            visited[k] = 1;
            //以k为中心点进行修正
            for (int i = 0; i < n; i++) {
                if(visited[i] == 0 && jz_time[start][k] + jz_time[k][i] < jz_time[start][i] ){
                    jz_time[start][i] = jz_time[start][k] + jz_time[k][i];
                    path[i] = path[k] + "--->" + temp[i];
                }
            }
        }
        
        System.out.println("从"+ temp[start]+ "出发到"+temp[arr]+"最短路径为："+ path[arr]);

        return shortPath;
    }
}
